package B刷题.KMP;

/**
 * @author wei.zhao
 * @description: 28.找出字符串中第一个匹配项的下标
 * @date 2022年09月14日 10:14
 */
public class Code01_KMP {

    public static int getIndexOf(String str, String match) {
        if (str == null || match == null || match.length() < 1 || str.length() < match.length()) {
            return -1;
        }
        int s = 0;
        int m = 0;
        char[] sChars = str.toCharArray();
        char[] mChars = match.toCharArray();
        int[] nextArr = getNextArr(mChars);
        while (s < sChars.length && m < mChars.length) {
            if (sChars[s] == mChars[m]) {
                s++;
                m++;
            } else if (nextArr[m] == -1) {
                s++;
            } else {
                m = nextArr[m];
            }

        }
        return m == mChars.length ? s - m : -1;
    }

    public static int[] getNextArr(char[] chars) {
        if (chars.length == 1) {
            return new int[]{-1};
        }
        int[] result = new int[chars.length];
        result[0] = -1;
        result[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < chars.length) {
            if (chars[i - 1] == chars[cn]) {
                result[i++] = ++cn;
            } else if (cn == 0) {
                result[i++] = 0;
            } else {
                cn = result[cn];
            }
        }
        return result;
    }

}
